#coding:utf8
class Solution:
    def restoreIpAddresses(self,s):
        def dfs(s, sub, ips, ip):
            if sub == 4:
                if s == "":
                    ips.append(ip[1:])
                return
            for i in range(1,4):
                if i <= len(s):
                    if int(s[:i])<=255:
                        dfs(s[i:],sub+1, ips, ip+'.'+s[:i])
                    if s[0] == "0":
                        break
        ips = []
        dfs(s,0,ips,'')
        return ips

s = Solution()
print s.restoreIpAddresses("11111")
'''
given "25525511135"
return ["255.255.11.135", "255.255.111.35"]

这是一道很经典的dfs的题目
'''
